package doing.normal_001_100;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import static com.study.util.LogUtil.info;

/**
 * 15. 3Sum  三数之和
 * <p>
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个
 * 元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 * <p>
 * 2019-04-22 7:55 AM
 **/
@SuppressWarnings("all")
public class ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        //i 截止到倒数第三个数
        for (int i = 0; i < nums.length - 2; i++) {
            //除了第一个外，跳过重复的数字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //当遍历到正数，后面必然不存在负数，直接跳出
            if (nums[i] > 0) {
                break;
            }
            for (List<Integer> list : uniqueTwoSum(nums, i + 1, -nums[i])) {
                list.add(0, nums[i]);
                res.add(list);
            }
        }
        return res;
    }

    public List<List<Integer>> uniqueTwoSum(int[] nums, int left, int target) {
        int l = left;
        int r = nums.length - 1;
        List<List<Integer>> res = new LinkedList<>();
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                l++;
            } else if (nums[l] + nums[r] > target) {
                r--;
            } else {
                //如果l == left 或者 r == nums.length - 1 ,意味着res里面还没有数据，所以不用判断是否重复
                if (l == left || r == nums.length - 1 || nums[l] != nums[l - 1] && nums[r] != nums[r + 1]) {
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[l]);
                    list.add(nums[r]);
                    res.add(list);
                }
                l++;
                r--;
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[] A = new int[]{-1, 0, 1, 2, -1, -4};
        List<List<Integer>> B = threeSum(A);
        for (int i = 0; i < B.size(); i++) {
            info(B.get(i));
        }
    }
}